669. 修剪二叉搜索树

#leetcode/tree/bst

669. 修剪二叉搜索树

Similar Question

leading to the advanced question

Solution Tips

方案一: DFS

因为需要同时删除节点和一半的子树, 所以不需要讨论 remove 的那三种情况

var trimBST = function(root, low, high) {
    // 不是自平衡的二叉树, 就是普通的 BST
    // 通过递归找到需要删除的节点, 返回需要保留的节点
    return dfs(root, low, high);
    function dfs(node, low, high) {
        if (node === null) return node;

        if (node.val < low) {
            // 该 node 以及自身左子树应该删除
            // 右子树则需要继续递归
            // 返回右子树递归的结果
            return dfs(node.right, low, high);
        }
        else if (node.val > high) {
            // 该 node 以及自身右子树应该删除
            // 左子树则需要继续递归
            // 返回左子树递归的结果替代自身, 相当于删除了自身以及右子树
            return dfs(node.left, low, high)
        }
        else {
            node.left = dfs(node.left, low, high)
            node.right = dfs(node.right, low, high)
        }

        return node;
    }
};